#!/usr/bin/python3
# coding: utf-8
# file: recursion_.py
# 尾递归
# 2018-06-12
import sys
 
class TailRecurseException(BaseException):
    def __init__(self, args, kwargs):
        print('zzz')
        self.args = args
        self.kwargs = kwargs
 
def tail_call_optimized(g):
    
    def func(*args, **kwargs):
        print('bbb')
        f = sys._getframe()
        # 为什么是grandparent, 函数默认的第一层递归是父调用,
        # 对于尾递归, 不希望产生新的函数调用(即:祖父调用),
        # 所以这里抛出异常, 拿到参数, 退出被修饰函数的递归调用栈!(后面有动图分析)
        if f.f_back and f.f_back.f_back \
            and f.f_back.f_back.f_code == f.f_code:     # 判断是否是被自身调用
            print('>')
            raise TailRecurseException(args, kwargs)    # 函数调用自己的时候抛出异常, 被下面捕获到, 并重新传参执行, 直到函数退出
        else:
            while 1:
                try:
                    print('xxx', args)
                    return g(*args, **kwargs)           # 递归函数
                except TailRecurseException as e:       # 捕获异常
                    args = e.args
                    kwargs = e.kwargs
                    print('???', args)
    func.__doc__ = g.__doc__
    return func
 
@tail_call_optimized
def factorial(n, acc=1):
    "calculate a factorial"
    print(n)
    if n == 0:
        return acc
    return factorial(n-1, n*acc)
 
print(factorial(4))
 
